package com.leetcode;

import java.util.ArrayDeque;
import java.util.HashSet;

public class WordLadder {
	public int ladderLength(String start, String end, HashSet<String> dict) {
		HashSet<String> visited = new HashSet<String>();
		ArrayDeque<Ladder> queue = new ArrayDeque<Ladder>();
		queue.add(new Ladder(start, 0));
		visited.add(start);
		
		while (!queue.isEmpty()) {
			Ladder next = queue.pop();
			String word = next.key;
			for (int j=0; j<word.length(); j++) {
				char[] ch = word.toCharArray();
				char cur = ch[j];
				for (char i='a'; i<='z'; i++) {
					if (i == cur) continue;
					ch[j] = i;
					String newWord = new String(ch);
					if (dict.contains(newWord) && !visited.contains(newWord)) {
						if (newWord.equals(end)) return next.step + 1;
						queue.add(new Ladder(newWord, next.step + 1));
						visited.add(newWord);
					}
				}
			}
		}
		
        return 0;
    }
	
	private class Ladder {
		String key;
		int step;
		public Ladder(String key, int step) {
			this.key = key;
			this.step = step;
		}
	}
}
